//给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图： 
//
// 
// 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记； 
// 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。 
// 
//
// 返回 图中最大连通组件的大小 。 
//
// 
//
// 
// 
//
// 示例 1： 
//
// 
//
// 
//输入：nums = [4,6,15,35]
//输出：4
// 
//
// 示例 2： 
//
// 
//
// 
//输入：nums = [20,50,9,63]
//输出：2
// 
//
// 示例 3： 
//
// 
//
// 
//输入：nums = [2,3,6,7,4,12,21,39]
//输出：8
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 2 * 10⁴ 
// 1 <= nums[i] <= 10⁵ 
// nums 中所有值都 不同 
// 
//
// Related Topics 并查集 数组 数学 👍 77 👎 0

package leetcode.editor.cn;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _952_LargestComponentSizeByCommonFactor {
    public static void main(String[] args) {
        Solution solution = new _952_LargestComponentSizeByCommonFactor().new Solution();
        int[] nums = {2,3,6,7,4,12,21,39};
        System.out.println(solution.largestComponentSize(nums));

    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    int[] parent;
    Map<Integer, Integer> map;
    public int largestComponentSize(int[] nums) {
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = 0; j < nums.length; j++) {
//                System.out.println("a: " + nums[i] + "-->b: " + nums[j] + "==> " + getGongYueShu(nums[i], nums[j]));
//            }
//        }
//        return -1;

        int n = nums.length;
        map = new HashMap<>(n);
        int index = 0;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            map.put(nums[i], index++);
            parent[i] = nums[i];
        }

        for (int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                int gongYueShu = getGongYueShu(nums[i], nums[j]);
                if (gongYueShu != 1) {
                    merge(nums[i], nums[j]);
                }
            }
        }
        int max = 0;
        Map<Integer, Integer> res = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int num = find(nums[i]);
            res.put(num, res.getOrDefault(num, 0) + 1);
            max = Math.max(max, res.get(num));
        }
        return max;
    }
    private void merge(int a, int b) {
        parent[map.get(find(a))] = find(b);
    }
    private int find(int a) {
        if (parent[map.get(a)] == a) {
            return a;
        } else {
            int tmp = parent[map.get(a)];
            parent[map.get(a)] = find(tmp);
            return parent[map.get(a)];
        }
    }

    private int getGongYueShu(int a, int b) {
        if (a == b) return a;
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        int sub = a - b;
        while (sub != b) {
            a = b;
            b = sub;
            if (a < b) {
                int tmp = a;
                a = b;
                b = tmp;
            }
            sub = a - b;
        }
        return b;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}